#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 每个元组 a, b, c 三个数组成
vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    // 从小到大 排序
    sort(nums.begin(), nums.end());
    for (int i = 0, len = nums.size(); i < len - 2; i++) {
        // 第一个数大于0，那么后面数都大于0，没有符合条件的元组了，直接返回
        if (nums[i] > 0) return result;

        // 对 a 去重
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        int left { i + 1 }, right { len - 1 };
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum > 0) {
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                result.push_back({ nums[i], nums[left], nums[right] });
                // 对 b 去重
                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                }
                // 每找到一个元组 双指针收缩
                left++;
                right--;
            }
        }
    }

    return result;
}

void printVector(vector<vector<int>>& nums) {
    for (int i = 0, len1 = nums.size(); i < len1; i++) {
        string str { "[" };
        for (int j = 0, len2 = nums[i].size(); j < len2; j++) {
            str += (to_string(nums[i][j]) + (j < len2 - 1 ? ", " : ""));
        }
        str += "]";
        cout << str << "\n";
    }
}

int main() {
    vector<int> arr {-1,0,1,2,-1,-4};
    vector<vector<int>> result = threeSum(arr);
    printVector(result);

    return 0;
}